package algorithm.disjoint.test;

import algorithm.disjoint.union.*;
import utility.Asserts;
import utility.Times;

/**
 * 项目名称: god
 * 包 名 称: algorithm.disjoint.test
 * 类 名 称: Main
 * 类 描 述: TODO
 * 创建时间: 2020/6/28 9:59 下午
 * 创 建 人: Justice
 */
public class Main {
    public static void main(String[] args) {
        testTime(new UnionFindQuickFind(count));
        testTime(new UnionFindQuickUnion(count));
        testTime(new UnionFindQuickUnionSize(count));
        testTime(new UnionFindQuickUnionRank(count));
        testTime(new UnionFindQuickUnionRankPathCompress(count));
        testTime(new UnionFindQuickUnionRankPathSplit(count));
        testTime(new UnionFindQuickUnionRankPathHalve(count));
        testGeneric(new GenericUnionFind<Student>());
    }

    static final int count = 10000;

    static void testTime(UnionFind uf) {
        uf.union(0, 1);
        uf.union(0, 3);
        uf.union(0, 4);
        uf.union(2, 3);
        uf.union(2, 5);

        uf.union(6, 7);

        uf.union(8, 10);
        uf.union(9, 10);
        uf.union(9, 11);

        Asserts.test(!uf.isSame(2, 7));

        uf.union(4, 6);

        Asserts.test(uf.isSame(2, 7));

        Times.check(uf.getClass().getSimpleName(), () -> {
            for (int i = 0; i < count; i++) {
                uf.union((int) (Math.random() * count),
                        (int) (Math.random() * count));
            }

            for (int i = 0; i < count; i++) {
                uf.isSame((int) (Math.random() * count),
                        (int) (Math.random() * count));
            }
        });
    }

    static void testGeneric(GenericUnionFind<Student> genericUnionFind) {
        Student st1 = new Student(1, "Ann");
        Student st2 = new Student(2, "Bob");
        Student st3 = new Student(3, "Cindy");
        Student st4 = new Student(4, "Dave");
        genericUnionFind.makeSet(st1);
        genericUnionFind.makeSet(st2);
        genericUnionFind.makeSet(st3);
        genericUnionFind.makeSet(st4);
        genericUnionFind.union(st1, st2);
        genericUnionFind.union(st3, st4);
        genericUnionFind.union(st1, st4);
        Asserts.test(genericUnionFind.isSame(st2, st3));
    }
}
